package com.ting.test.algorithms.图;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 特点：有向无负
 */
public interface 迪瑞克斯拉算法1 {
    public static void main(String[] args) {
        process(new Node(3));
    }

    static void process(Node node) {
        if (null == node) {
            return;
        }

        HashMap<Node, Integer> distanceMap = new HashMap<>();
        HashSet<Node> selectedNodes = new HashSet<>();//存储已经确定的节点
        //所有的距离都是从节点node到某一个节点的距离，因此节点node自己到自己的距离是0
        distanceMap.put(node, 0);
        Node minNode = getMinDistenceNode(distanceMap, selectedNodes);
        while (minNode != null) {
            for (Edge edge : minNode.edges) {//遍历从当前节点出发的边
                Node to = edge.getTo();
                Integer newDistance = distanceMap.get(edge.getFrom()) + edge.getWeight();
                if (distanceMap.containsKey(to)) {//
                    //如果to节点已经存在于map中，则表明已经有一条通路从节点node到节点to
                    //现在就需要比较已经存在的通路和当前的通路哪个更短

                    //取出已经存在的从node到to的距离
                    Integer oldDistance = distanceMap.get(to);
                    distanceMap.put(to, Math.min(newDistance, oldDistance));

                } else {
                    //如果to节点不再map中，则表明之前还米有从node到to的通路
                    distanceMap.put(to, newDistance);
                }
            }
            selectedNodes.add(minNode);//这块没太懂
            minNode = getMinDistenceNode(distanceMap, selectedNodes);

        }
    }

    /**
     * 从map中获取一个截止目前从node到该节点距离最短，但是还没有确定最终距离的节点
     *
     * @param distanceMap
     * @param selectedNodes
     * @return
     */
    static Node getMinDistenceNode(HashMap<Node, Integer> distanceMap, HashSet<Node> selectedNodes) {

        int distance = Integer.MAX_VALUE;
        Node result = null;
        for (Node node : distanceMap.keySet()) {
            if (distanceMap.get(node) < distance && !selectedNodes.contains(node)) {
                result = node;
                distance = distanceMap.get(node);
            }

        }
        return result;
    }
}
